package com.atguigui.leetcode;

/**
 * Java：买卖股票的最佳时机含手续费
 *
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2020/12/17 4:53 下午
 */
public class P714BestTimeToBuyAndSellStockWithTransactionFee {
    public static void main(String[] args) {
        Solution solution = new P714BestTimeToBuyAndSellStockWithTransactionFee().new Solution();
        System.out.println(solution.maxProfit(new int[]{1, 3, 2, 8, 4, 9}, 2));
        // TO TEST
    }
    class Solution {
        public int maxProfit(int[] prices, int fee) {
            int n = prices.length;
            int[][] dp = new int[n][2];
            //手里没有股票的时候，第一天收益为0
            dp[0][0] = 0;
            //手里有股票的时候，第一天必定亏
            dp[0][1] = -prices[0];

            for (int i = 1; i < n; ++i) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }

            return dp[n - 1][0];
        }
    }
}
